|
In cryptanalysis, Kasiski examination (also referred to as Kasiski's Test or Kasiski's Method) is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher.〔 〕〔 〕 It was first published by Friedrich Kasiski in 1863,〔Kasiski, F. W. 1863. Die Geheimschriften und die Dechiffrir-Kunst. Berlin: E. S. Mittler und Sohn〕 but seems to have been independently discovered by Charles Babbage as early as 1846.〔Franksen, O. I. 1985 Mr. Babbage's Secret: the Tale of a Cipher—and APL. Prentice Hall〕〔 〕 == How it works == In polyalphabetic substitution ciphers where the substitution alphabets are chosen by the use of a keyword, the Kasiski examination allows a cryptanalyst to deduce the length of the keyword. Once the length of the keyword is discovered, the cryptanalyst lines up the ciphertext in ''n'' columns, where ''n'' is the length of the keyword. Then, each column can be treated as the ciphertext of a monoalphabetic substitution cipher. As such, each column can be attacked with frequency analysis.〔 〕Similarly, where a rotor stream cipher machine has been used, this method may allow the deduction of the length of individual rotors. The Kasiski examination involves looking for strings of characters that are repeated in the ciphertext. The strings should be three characters long or more for the examination to be successful. Then, the distances between consecutive occurrences of the strings are likely to be multiples of the length of the keyword. Thus finding more repeated strings narrows down the possible lengths of the keyword, since we can take the greatest common divisor of all the distances. The reason this test works is that if a repeated string occurs in the plaintext, and the distance between corresponding characters is a multiple of the keyword length, the keyword letters will line up in the same way with both occurrences of the string. For example, consider the plaintext: crypto is short for cryptography. "crypto" is a repeated string, and the distance between the occurrences is 20 characters. We will line up the plaintext with, first, a six-character keyword "abcdef" (6 does not divide 20) and a five-character keyword "abcde" (5 divides 20). abcdefabcdefabcdefabcdefabcdefabc crypto is short for cryptography. Notice that the first instance of "crypto" lines up with "abcdef" and the second instance lines up with "cdefab". The two instances will encrypt to different ciphertexts and the Kasiski examination will reveal nothing. abcdeabcdeabcdeabcdeabcdeabcdeabc crypto is short for cryptography. Note that both occurrences of "crypto" now line up with "abcdea". The two instances will encrypt to the same ciphertext and the Kasiski examination will be effective. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kasiski examination」の詳細全文を読む スポンサード リンク
|